【题解】 [HNOI2019]校园旅行 生成树+DP luoguP5292 | Qiuly's blog!

【题解】 [HNOI2019]校园旅行 生成树+DP luoguP5292

Posted on | Edited on | In | Comments:

$myy$ 出的神题……貌似正解并不难但是没有人切……

$30$ 分可以用 $DP$ ，设 $f[i][j]$ 表示 $i$ 到 $j$ 是否有一条满足条件的路径。对于有一条满足条件的路径的 $i,j$ ，我们枚举连接 $i$ 的点和连接 $j$ 的点，如果这两个点的标记相同，那么既然 $i,j​$ 合法，这两个点也一定合法。

不过这样的复杂度是 $O(m^2)$ 的，所以只能过 $30$ 分。

然后考虑优化，我们发现所有的边也就只有三种：

  • 该边连接的两个点的标记相同
    • 两个点的标记都为 $1$
    • 两个点的标记都为 $0​$
  • 改边连接的两个点的标记不同

然后我们开 $3$ 个图，对于每一条读入进来的边，如果属于第一种就插入到第一个图中，其他同理。

然后会发现这三个图都是有若干个连通块组成的，可以知道，如果我们留下来的仅是该连通块的生成树也不会对答案产生影响，但是边数却大大减少！

但是直接对每个连通块求生成树是不对的，因为生成树上任意两个点之间的路径经过的边的条数的奇偶是确定的，并且只有二分图满足该条件，不过我们无法保证连通块是二分图，也就是说，连通块中的任意两个点之间的路径经过的边的条数的奇偶是不确定的。

那么我们现在需要做的就是，如何使得不是二分图的连通块所求出的生成树可以满足——任意两个点之间的路径经过的边的条数的奇偶是不确定的。

仔细想想后发现并不难，我们只需要在生成树上加上一个奇环就好了，当然也等价于在生成树上的某一个点上加个自环。

这就很好办了，现在我们的边数已经大大减少了，这个时候再跑原先的 $30$ 分算法就可以过了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define MKP make_pair

const int N=5e3+7;
const int M=5e5+7;

int n,m,q,s[N],vis[N],f[N][N];
int flag,sta[N],top;
template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

struct Graph {
    int head[N],nxt[M<<1],to[M<<1],from[N],cnt;
    void ins(int u,int v) {
        ++cnt,nxt[cnt]=head[u],to[cnt]=v,head[u]=cnt;
        ++cnt,nxt[cnt]=head[v],to[cnt]=u,head[v]=cnt;
    }
    void check(int u,int col) {
        vis[u]=col,sta[++top]=u;
        for(int i=head[u];i;i=nxt[i])
            if(!vis[to[i]]) from[to[i]]=u,check(to[i],3-col);
            else flag|=(vis[to[i]]!=3-col);
    }
    void solve() {
        queue<pair<int,int> > q;
        while(!q.empty()) q.pop();
        for(int i=1;i<=n;++i) f[i][i]=1,q.push(MKP(i,i));
        for(int i=1;i<=n;++i)
            for(int j=head[i];j;j=nxt[j])
                if(s[i]==s[to[j]]) f[i][to[j]]=1,q.push(MKP(i,to[j]));
        while(!q.empty()) {
            int x=q.front().first,y=q.front().second,u,v;
            q.pop();
            for(int i=head[x];i;i=nxt[i])
                for(int j=head[y];j;j=nxt[j]) 
                    if(!f[u=to[i]][v=to[j]]&&s[u]==s[v])
                        f[u][v]=f[v][u]=1,q.push(MKP(u,v));
        }return;
    }
}G[3],t;

char str[N];
int main() {
    IN(n),IN(m),IN(q);
    scanf("%s",str);
    for(int i=0;i<n;++i) s[i+1]=str[i]-'0';
    for(int i=1;i<=m;++i) {
        int x,y;IN(x),IN(y);
        if(s[x]==s[y]) {
            if(s[x]) G[0].ins(x,y);
            else G[1].ins(x,y);
        } else G[2].ins(x,y);
    }
    for(int k=0;k<=2;++k) {
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;++i) if(!vis[i]) {
            flag=top=0,G[k].check(i,1);
            while(top) {
                int x=sta[top];
                if(G[k].from[x]) t.ins(G[k].from[x],x);
                --top;
            }if(flag) t.ins(i,i);
        }
    }
    t.solve();
    for(int i=1,x,y;i<=q;++i) 
        IN(x),IN(y),printf(f[x][y]?"YES\n":"NO\n");
    return 0;
}

额……其实这份代码在 $luogu$ 上会被卡成 $70$ ，不过那是在没开 $O2$ 的情况下的，开了 $O2$ 顿时飞起！(幸好这题在考场上就是开 $O2$ 的)。

本文标题:【题解】 [HNOI2019]校园旅行 生成树+DP luoguP5292

文章作者:Qiuly

发布时间:2019年04月14日 - 00:00

最后更新:2019年04月18日 - 09:59

原始链接:http://qiulyblog.github.io/2019/04/14/[题解]luoguP5292/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。